﻿#include <iostream>

// n是否是质数?
static bool isPrim(int n)
{
    if (n == 1) return false;

    int sqrtN = (int) sqrt(n);
    for (int i = 2; i <= sqrtN; i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}

/**
  * n可以拆分为多个质数的乘积, 比如 15=3*5
  * @param n
  * @return 设返回的数组是arr，arr[0]是这些质数的和，arr[1]是这些质数的个数，对于15，返回 { 8, 2 },
  * ∵ 3 + 5 = 8;
  */
static int* divsSumAndCount(int n)
{
    int sum = 0;
    int count = 0;
    for (int i = 2; i <= n; i++)
    {
        while (n % i == 0)
        {
            sum += i;
            count++;
            n /= i;
        }
    }

    return new int[] { sum, count };
}

static int minCount(int n) {
    if (n == 1) {
        return 0;
    }

    if (isPrim(n)) {
        return n - 1;
    }

    int* arr = divsSumAndCount(n);
    int offset = arr[0] - arr[1];
    free(arr);
    return offset;
}

/**
 * 假设s和m初始化，s = "a"; m = s;
 * 再定义两种操作，第一种操作:
 * m = s;
 * s = s + s;
 * 第二种操作:
 * s = s + m;
 * 求最小的操作步骤数，可以将s拼接到长度等于n
 *
 * 思路：
 * 1. 如果n是质数，则最小的操作步骤用第二种操作即可堆出，即使使用了第一种操作，也无法减少操作次数。
 * 2. 如果n不是质数，则将n拆解为质数的乘积，比如a*b(a和b都为质数)，则最小的操作步骤是 a-1+b-1;
 * a*b*c, 则最小的操作步骤是 a-1+b-1+c-1
 */
int main_JoinToLengthN()
{
    for (int i = 1; i < 100; i++) {
        //            int* arr = divsSumAndCount(i);
        //            printf("[%d]%d,%d\n", i, arr[0], arr[1]);
        printf("[%d]->%d\n", i, minCount(i));
    }
 
    return 0;
}